Heavy Light Decomposition

설명

현재노드 x의 자식노드들 중에서 제일 서브트리사이즈가 큰쪽으로 chain을 연장하고, 나머지 자식들에서는 새로운 chain을 시작한다. 그러면 모든 노드는 하나의 chain에 속하게 된다. 이렇게 HLD로 트리를 chain들로 분해했을때, 임의의 경로(u,v)를 구성하는 chain의 갯수는 O(logN)을 넘지 않는다.

Proof

일단, 임의의 경로를 w=LCA(u,v)를 기준으로 두 개의 경로(w,u),(w,v)로 나누어봅시다. (w,u)의 chain갯수는 O(logN)을 넘지 않는데, 그 이유는 x에서 자식ch로 갈때 새로운 chain을 만들기 위해서는 tsz[x]/2이하여야 하기 때문에(초과면 정의상 새로운 chain을 만들지 않고 기존chain을 연장해야함) 항상 사이즈가 반으로 줄어들고, 따라서 최대 log번정도만 새로운 chain을 만들 수 있다. (w,v)경로도 같은 이유로 log번정도만 새로운 chain이 생성되므로, 전체경로(u,v)는 O(logN)개의 chain으로 구성된다. chain이 log개인것이 왜 유용할까? 모든 chain에 대해, 한 chain내의 정점들의 prefix-order(dfs order라고도 함)가 연속하도록 넘버링을 잘 해준다면, 한 chain에 대해서는 하나의 구간쿼리로 처리해줄 수 있고, 따라서 임의의 경로는 log개의 chain으로 분해되므로 log번의 쿼리로 풀 수 있게 된다.